1. Field of the Invention
The present invention relates to probabilistic pointer analysis method.
2. Description of the Related Art
Pointer analysis is a compiler analysis technique that statically estimates the possible runtime values of a pointer. Due to the dynamic association property of pointers in programs, it is difficult for compilers to know where pointers may point to in general. Without such knowledge, conservative assumptions of pointer information must be made, which may impede aggressive optimizations. There have been considerable efforts on this topic by researchers, and many intra- and inter-procedural pointer analysis algorithms have been developed. In addition, computational cost of gathering pointer information needs to be taken into consideration.
The pointer information gathered by the traditional points-to analysis techniques can be categorized into two types. The first type is definitely-points-to relationships, and the second type is possibly-points-to relationships. For possibly-points-to relationships, the pointer information gathered by the traditional techniques is not precise enough for certain optimization-directed analyses, as it only shows that there is a possibility for one pointer to be located in a location, but fails to show the likelihood. Accordingly, quantitative descriptions are needed for modern compiler optimizations.
Probabilistic points-to analysis (PPA) techniques have been proposed to quantify points-to relationships. Optimizations that can potentially benefit from such compiler information include speculative multithreading execution, data speculation, data pre-fetching, transactional memory, and others. Opportunities can be explored according to the likelihood provided by PPA for follow-up optimizations. In fact, PPA was originally designed to provide a set of transfer functions of data flow analysis for each pointer usage. When the data flow analysis converges, equations must be solved to get probabilistic information. However, the amount of information collected by the data flow analysis is usually large, and consequently the compiler analysis of previous PPA techniques is not efficient for practical use.
In order to reduce the cost of pointer analysis, the present invention discloses a static single assignment (SSA) based approach such that the related locations or addresses of a target pointer can be traced with lower costs.